1. Field
The embodiments relate to rewriting a branching prediction bit of a binary program.
2. Description of the Related Art
Recently, to prevent disorder of processing sequences in pipeline processing work flows, pipeline processing computers implement a function of predicting whether a conditional branch will be taken. A computer with this function, when executing a branch instruction where the branch is predicted to be taken, pre-fetches a subsequent group of instructions under the assumption that the branching condition has been met. If the prediction is wrong, the computer discards the group of instructions pre-fetched and newly pre-fetches a group of instructions for the case where the branching condition has not been met and accordingly, extra time, namely, branch penalty, is caused.
Branch predicting functions include a static branch predicting function of explicitly specifying a branching direction from software. Regarding this static branch predicting function, a binary program converting apparatus is known that converts a binary program to the binary program to be executed by a computer with a branch predicting unit.
FIG. 20 is a diagram of a configuration of a conventional binary program converting apparatus. As shown in FIG. 20, this binary program converting apparatus comprises a binary program converting tool 4 and a tracer 2. In advance, the tracer 2 executes a pre-conversion binary program 1 composed of plural instruction blocks and generates trace information 3 based on execution information collected from such execution. The trace information 3 is the result of totaling, according to binary programs or instruction blocks, an operation history (trace information) extracted at the time of execution of the pre-conversion binary program 1.
The instruction block is a part of the binary program partitioned by control transfer instructions such as the branch instruction, a jump instruction, and a call instruction or a block defined by partitioning a program area so that the head becomes a label as a branch destination of the branch instruction. The binary program converting tool 4, upon receipt of the trace information 3, generates a post-conversion binary program 5 from the pre-conversion binary program 1.
In such a conversion, the binary program converting tool 4 changes the arrangement of the instruction blocks so that, when the computer has a characteristic of predicting branching execution probability to be low with respect to the branch instruction to an address in the upward direction (or downward direction), the branch instruction having a low frequency of branching will be the branch instruction to the address in the upward direction (or downward direction) and the branch instruction having a high frequency of branching will be the branch instruction to the address in the downward direction (upward direction). The binary program converting tool 4 also changes the arrangement of the instruction blocks so that, with respect to the branch instruction having a high frequency of branching, a part corresponding to the instruction block before the branching and a part corresponding to the instruction block after the branching will be continuous with each other, such as that disclosed in Japanese Patent Application Laid-Open Publication No. 2001-273138, paragraphs [0011] to [0020] and [0038].
However, the conventional technology disclosed in Japanese Patent Application Laid-Open Publication No. 2001-273138 has the following problems. Firstly, since a sequence of instructions is replaced with another sequence of instructions and the instruction block is caused to move, instruction code length is increased or decreased and code size is expanded in some cases. For this reason, this technology is not suitable for a built-in system for which restriction on capacity size is severe. Secondly, in the case of the built-in system, the trace information is acquired by a simulator. Usually, since an executable format program to be executed on the simulator is different from the executable format program to be executed on a device in which the built-in system is actually incorporated (hereinafter, actual machine), the trace information obtained by the simulator may not be directly used for processing the executable format program for the actual machine.
Thirdly, since consideration is not given to a case where there are plural execution paths for the same branch instruction, it is not clear from which execution path the trace information obtained should be used in preparing or processing the program corresponding to the branch predication. Fourthly, the criteria for judging whether the branch is taken in the branch instruction are based on the number of times the branch has been taken at the time of the program execution to obtain the trace information and do not reflect the branch penalty. Therefore, though the hit rate of the branch prediction is high, there are cases where the branch penalty is not sufficiently decreased.